﻿#include<stdio.h>
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;

template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K,V>& kv)
		: _kv(kv)
		, _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _bf(0)
	{}

	pair<K, V> _kv;
	AVLTreeNode<K,V>* _pLeft;
	AVLTreeNode<K,V>* _pRight;
	AVLTreeNode<K,V>* _pParent;
	int _bf;   // 节点的平衡因子，左减右
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class K,class V>
class AVLTree   //右大左小
{
	typedef AVLTreeNode<K,V> Node;
public:
	AVLTree()
		: _pRoot(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const pair<K, V>& kv)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(kv);
			_size++;
			return true;
		}

		Node* cur = _pRoot;

		while (cur != nullptr)//插入
		{
			if (kv.first < cur->_kv.first)
			{
				cur->_bf++;
				if (cur->_pLeft != nullptr)
				{
					cur = cur->_pLeft;
				}
				else
				{
					cur->_pLeft = new Node(kv);
					cur->_pLeft->_pParent = cur;
					break;
				}

			}
			else if (kv.first > cur->_kv.first)
			{
				cur->_bf--;
				if (cur->_pRight != nullptr)
				{
					cur = cur->_pRight;
				}
				else
				{
					cur->_pRight = new Node(kv);
					cur->_pRight->_pParent = cur;
					break;
				}
			}
			else
			{
				assert(0);
			}

		}

		while (cur != nullptr)//旋转
		{
			if (cur->_bf == 2)
			{
				if (cur->_pLeft->_bf >= 0)//一边高，单旋
				{
					RotateR(cur);
				}
				else//异边高，双旋
				{
					RotateLR(cur);
				}
			}
			else if (cur->_bf == -2)
			{
				if (cur->_pRight->_bf <= 0)//一边高，单旋
				{
					RotateL(cur);
				}
				else//异边高，双旋
				{
					RotateRL(cur);
				}
			}
			else
			{
				cur = cur->_pParent;
			}
		}
		_size++;
	}

	void _InOrder(Node* root) 
	{
		if (root == nullptr)
			return;
		else
		{
			_InOrder(root->_pLeft);
			cout<<root->_kv.first<< endl;
			_InOrder(root->_pRight);
		}
	}

	void InOrder()
	{
		_InOrder(_pRoot);
	}



	int Size()
	{
		return _size;
	}

	size_t Height()
	{
		return _Height(_pRoot);
	}

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot)
	{
		bool key = true;
		if (abs(pRoot->_bf) >= 2)
		{
			return false;
		}
		else
		{
			if (pRoot->_pLeft != nullptr)
			{
				key = _IsAVLTree(pRoot->_pLeft);
			}
			if (pRoot->_pRight != nullptr)
			{
				key= key && _IsAVLTree(pRoot->_pRight);//有一个子树不平衡就不是AVL树，所以不能用true覆盖false;
			}
			return key;
		}
	}





	size_t _Height(Node* pParent)
	{
		if (pParent == nullptr)
		{
			return 0;
		}

		size_t lh = _Height(pParent->_pLeft);
		size_t rh = _Height(pParent->_pRight);

		if (lh > rh)
			return ++lh;
		else
			return ++rh;
	}
	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* temp = pParent->_pLeft;
		pParent->_pLeft = temp->_pRight;
		temp->_pRight = temp->_pParent;
		temp->_pParent = pParent->_pParent;
		pParent->_pParent = temp;

		if (pParent->_pLeft != nullptr)
		{
			pParent->_pLeft->_pParent = pParent;
		}

		if (temp->_pParent == nullptr)
		{
			_pRoot = temp;
			temp->_pParent = nullptr;
		}
		else
		{
			if (pParent == temp->_pParent->_pLeft)
			{
				temp->_pParent->_pLeft = temp;
			}
			else if (pParent == temp->_pParent->_pRight)
			{
				temp->_pParent->_pRight = temp;
			}
			else
			{
				assert(false);
			}
		}
		temp->_bf = pParent->_bf = 0;
	}

	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* temp = pParent->_pRight;
		pParent->_pRight = temp->_pLeft;
		temp->_pLeft = temp->_pParent;
		temp->_pParent = pParent->_pParent;

		pParent->_pParent = temp;
		if (pParent->_pRight != nullptr)
		{
			pParent->_pRight->_pParent = pParent;
		}

		if (temp->_pParent == nullptr)
		{
			_pRoot = temp;
			temp->_pParent = nullptr;
		}
		else
		{
			if (pParent == temp->_pParent->_pLeft)
			{
				temp->_pParent->_pLeft = temp;
			}
			else if (pParent == temp->_pParent->_pRight)
			{
				temp->_pParent->_pRight = temp;
			}
			else
			{
				assert(false);
			}
		}
		temp->_bf = pParent->_bf = 0;
	}

	// 右左双旋
	void RotateRL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		int bf = pParent->_pRight->_pLeft->_bf;

		RotateR(pParent->_pRight);
		RotateL(pParent);

		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			pParent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			pParent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	// 左右双旋
	void RotateLR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		int bf = subLR->_bf;

		RotateL(pParent->_pLeft);
		RotateR(pParent);

		if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			pParent->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			pParent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

private:
	Node* _pRoot;
	int _size=0;
};

void TestAVLTree1()
{
	AVLTree<int, int> t;
	// 常规的测试⽤例
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.Insert({ e, e });
	}
	t.InOrder();
	cout << t.IsAVLTree() << endl;
}


int main()
{
	TestAVLTree1();
	return 0;
}